백준 2887번 - 행성 터널

문제링크

문제풀이

간선을 직접 구해야하는 최소신장트리 문제 이다.
간선을 구하는 과정만 해결하면 이후의 과정은 일반적인 최소신장 트리와 같다.

가중치는 $min(|xA-xB|,|yA-yB|,|zA-zB|)$이다.
최소신장트리를 형성하는 간선을 선택할 때는 사이클을 형성하지 않으면서 가중치가 작은 간선들 부터 선택하기 때문에 모든 간선을 구하는 것이 아니라 각 노드별로 가중치가 작은 간선만 구하면된다.

결국 좌표계에서의 차이가 가중치가 되기 때문에 가중치가 최소 인것은 정렬한 뒤에 자신과 앞뒤로 있는 노드와의 차이가 된다.
그래서 x,y,z 좌표별로 각각 정렬을 해준 다음에 앞에서부터 i와 i+1번째 노드를 잇는 간선을 구해줬다.
그렇게 되면 각 좌표계별로 n-1개씩 총 3n-3개의 간선이 생긴다.
이 간선들을 기반으로 최소신장트리#Kruskal MST 알고리즘 을 적용해주면 된다.

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const input = [];
rl.on("line", (line) => {
  input.push(line.split(" ").map((x) => Number(x)));
});
rl.on("close", () => {
  const n = input[0][0];
  let stars = input.slice(1);
  stars = stars.map((v, idx) => [idx, ...v]);
  const edges = [];
  for (let i = 1; i <= 3; i++) {
    stars.sort((a, b) => a[i] - b[i]);
    for (let j = 0; j < n - 1; j++) {
      edges.push([stars[j][0], stars[j + 1][0], stars[j + 1][i] - stars[j][i]]);
    }
  }
  edges.sort((a, b) => b[2] - a[2]);
  const parent = Array.from(Array(n), (x, idx) => idx);
  let result = 0;
  let t = 0;
  while (t < n - 1) {
    const [a, b, c] = edges.pop();
    const aParent = find(a);
    const bParent = find(b);
    if (aParent == bParent) {
      continue;
    }
    union(aParent, bParent);
    result += c;
    t++;
  }
  console.log(result);

  function find(x) {
    let y = x;
    while (y != parent[y]) {
      y = parent[y];
    }
    parent[x] = y;
    return y;
  }
  function union(x, y) {
    parent[x] = parent[y];
  }
});